package 力扣._494_目标和;

import java.util.Arrays;

public class Solution {
    public int findTargetSumWays(int[] nums, int target) {
        //分成加法集合s1, 减法集合s2, 则 s1-s2 = t, s1+s2 = sum;
        //解得 s1 = (sum+t)/2 , s2 = (sum-t)/2 若不可整除则直接false，毕竟整数凑不出非整数
        //dp[j] 装满容量为j的背包有dp[j]种方法
        //dp[j] += dp[j-nums[i]]
        //价值与重量相同
        int sum = 0;
        for (int num : nums) {
            sum += num;
        }
        if ((sum + target) % 2 != 0||(sum + target)<0)
            return 0;
        int m = (sum + target) / 2;
        int[] dp = new int[m + 1];
        dp[0] = 1; //装满背包容量为1的背包，有一种方法——》不放东西
        for (int i = 0; i < nums.length; i++) {
            for (int j = m; j >= nums[i]; j--) {
                dp[j] += dp[j - nums[i]];
            }
        }
//        System.out.println(Arrays.toString(dp));
        return dp[m];
    }

    public static void main(String[] args) {
        System.out.println(new Solution().findTargetSumWays(new int[]{100}, -200));
    }
}
